package com.leetcode.partition2;

import com.leetcode.common.TreeNode;

import java.util.Objects;

/**
 * @author `RKC`
 * @date 2021/8/19 9:19
 */
public class LC105从前序与中序遍历序列构造二叉树 {

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) return null;
        return divide(preorder, inorder, 0, preorder.length, 0, inorder.length);
    }

    public static void main(String[] args) {
        int[] preorder = { 1, 2, 4, 5, 3, 6, 7 };
        int[] inorder = { 4, 5, 2, 1, 6, 7, 3 };
        System.out.println(Objects.requireNonNull(buildTree(preorder, inorder)).val);
    }

    @SuppressWarnings("UnnecessaryLocalVariable")
    private static TreeNode divide(final int[] preorder, final int[] inorder, int preorderStart, int preorderEnd, int inorderStart, int inorderEnd) {
        if (preorderStart == preorderEnd) return null;
        //取出前序序列在有效区间的第一个值，作为标准在中序序列中进行切割
        int value = preorder[preorderStart];
        TreeNode root = new TreeNode(value);
        if (preorderEnd - preorderStart == 1) return root;
        int delimiterIndex = 0;
        for (delimiterIndex = inorderStart; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == value) break;
        }
        //切割前序序列
        int leftPreorderStart = 1 + preorderStart, leftPreorderEnd = leftPreorderStart + delimiterIndex - inorderStart;
        int rightPreorderStart = leftPreorderEnd, rightPreorderEnd = preorderEnd;
        //切割中序序列
        int leftInorderStart = inorderStart, leftInorderEnd = delimiterIndex;
        int rightInorderStart = leftInorderEnd + 1, rightInorderEnd = inorderEnd;
        System.out.printf("左前：[%d, %d), 右前：[%d, %d)\t左中：[%d, %d)，右中：[%d, %d)\n", leftPreorderStart, leftPreorderEnd, rightPreorderStart, rightPreorderEnd, leftInorderStart,
                leftInorderEnd, rightInorderStart, rightInorderEnd);
        root.left = divide(preorder, inorder, leftPreorderStart, leftPreorderEnd, leftInorderStart, leftInorderEnd);
        root.right = divide(preorder, inorder, rightPreorderStart, rightPreorderEnd, rightInorderStart, rightInorderEnd);
        return root;
    }
}
